There are many situations in which it may be useful to perform interpolation on an array of data points to thereby determine an interpolated value at a sampling position within the array. In general, an array of data points may be an n-dimensional array where n≥1. For example, in graphics processing systems a two dimensional (2D) array of texels can be stored to describe a texture, and when the texture is to be applied at a pixel position of an image, the pixel position might not correspond exactly with the position of a texel in the texture, so an interpolated value of the texture at the pixel position (i.e. at a sampling position) is desired. As another example, a 2D array of pixels may represent an image, and if the image is to be scaled then the new pixel positions might not correspond exactly with the positions of original pixels in the image, so interpolated values at the new pixel positions (i.e. at sampling positions) are desired.
FIG. 1 shows an example of part of a 2D array 100 of data points 102. FIG. 1 shows a 4×4 set of the data points 102 of the array 100, and as an example two parameters (U and V) describe a sampling position 106 within a region 104 for which an interpolation can be performed.
Interpolation can be performed in a number of different ways. Piecewise linear interpolation is an example of a 1D interpolation method which is simple to implement. An example of linear interpolation is shown in FIG. 2a in which an interpolated value can be determined at a sampling position between two data points A and B. A straight line 202 between the data points A and B shows the interpolated values at sampling positions between the data points A and B. The sampling position is given by the parameter, u, where 0≤u≤1, such that the interpolated value lu at the sampling position is given by a weighted sum: Iu=(1−u)A+uB.
Bilinear interpolation is an example of a 2D interpolation method which extends the concept of linear interpolation into two dimensions. An example of bilinear interpolation is shown in FIG. 2b in which an interpolated value can be determined at a sampling position 208 within a square of four surrounding data points 2041, 2042, 2043 and 2044. The sampling position 208 is given by two parameters (U and V). When confronted with a multi-dimensional interpolation, one approach is to reduce the dimensionality of the problem, e.g. by performing a separate 1D interpolation for each of the rows, and then performing a 1D interpolation over those results. For example, a linear interpolation can be performed between the data points 2041 and 2042, using the parameter U, to determine the intermediate interpolated value 2061. Similarly, a linear interpolation can be performed between the data points 2043 and 2044, using the parameter U, to determine the intermediate interpolated value 2062. Then a linear interpolation can be performed between the intermediate interpolated values 2061 and 2062, using the parameter V, to determine the interpolated value 208 at the sampling position given by (U,V). The three linear interpolations described in this bilinear interpolation method can be performed in the same way as the linear interpolation described above with reference to FIG. 2a. An example of reducing the dimensionality of a multi-dimensional filtering problem is described in Mitchell and Netravali's 1988 SIGGRAPH paper “Reconstruction Filters in Computer Graphics”, which explains that image reconstruction takes place in two dimensions and involves the convolution of a 2D lattice of samples with a filter k(x,y). Separable filters are considered, where the samples are convolved with the product k(x)k(y). The Mitchell and Netravali paper describes that separable filters are computationally more efficient than nonseparable filters because the filtering operation can be performed in separate passes vertically and horizontally.
Bilinear interpolation can be implemented in a simple manner in hardware, e.g. using some multiply and add (MAD) logic. Furthermore, bilinear interpolation is a fast process which does not consume a large amount of power. Therefore, bilinear interpolation may often be an appropriate choice for interpolation implemented in computer systems which have particularly limited processing power, e.g. in mobile devices such as smart phones, tablets and laptops.
However, linear and bilinear interpolation might not provide smooth interpolated values. In particular, although linear and bilinear interpolation methods will provide interpolated values which are continuous, the first derivative (and higher order derivatives) of the interpolated values is typically not continuous over the data point boundaries. Higher order polynomial interpolation, e.g. quadratic, cubic, quartic, etc—based and their multidimensional variants methods provide smoother interpolated values than the corresponding linear and bilinear interpolation methods. Of particular interest is cubic interpolation as this is the simplest polynomial which can interpolate (i.e. pass through) the control points and where the first derivative of the interpolated values can be continuous over the data point boundaries. Cubic interpolation methods (including multidimensional cubic interpolation methods such as bicubic interpolation methods) match interpolated values and the first derivative of the interpolated values over data point boundaries. However, cubic interpolation methods are more complex to implement than linear interpolation methods (including the corresponding multidimensional linear interpolation methods such as bilinear interpolation methods). Some reasons for this are that cubic interpolation uses twice as many data points in each dimension of the array compared to linear interpolation (and thus bicubic requires 4× as many data points as bilinear interpolation), and cubic interpolation comprises computing third degree polynomials for a sampling position within the array. Therefore, as an example, bicubic interpolation may be chosen over bilinear interpolation when computation speed is not an issue. A person skilled in the art will be aware that there are many types of control-point based cubic curves, including Bezier, Hermite and BSpline, and although each can be mapped into each other by taking linear combinations of the control/sampling points (e.g. see “Computer Graphics Principles and Practice”, Second Edition, pp 510 and 511 by Foley, van Dam et al) and, in a broad sense, are equivalent, one of particular interest is the Catmull-Rom spline. This has the useful property that if the sampling position lies exactly on a data point (e.g. if U=0 or U=1) then the interpolated value equals the value of the data point. Further, as described below, when neighbouring curves share three sample points then the curves are also C1 continuous, i.e. the first derivatives of the curves are continuous.
An example of 1D cubic interpolation is shown in FIG. 3a in which four data points (A to D) are used to determine an interpolated value (lu) at a sampling position between the two central data points B and C. A line 302 shows the interpolated values, and it can be seen that the line 302 passes through the data points B&C and that the gradient of the line 302 (i.e. the first derivative of the line 302) is continuous with the neighbouring piecewise segments, 302AB and 302CD, at the curve boundaries. The sampling position is given by the parameter, u, for the region 0≤u≤1. As described above, the interpolated value lu can be found according to a third degree polynomial which takes the parameter u and the four data points (A to D) as inputs.
Bicubic interpolation is an example of a 2D interpolation method which extends the concept of cubic interpolation into two dimensions. An example of bicubic interpolation is shown in FIG. 3b in which an interpolated value can be determined at a sampling position 308 within a 2×2 square of data points 30422, 30423, 30432 and 30433 using the values of the data points 30411 to 30444. The sampling position 308 is given by two parameters (U and V). In this example, a cubic interpolation can be performed separately for each of the four rows of data points (e.g. data points 304x1 to 304x4 for row x), using the parameter U, to determine a respective intermediate interpolated value 306x. In this way the dimensionality of the interpolation computation has been reduced. Then a cubic interpolation can be performed over the four intermediate interpolated values 3061 to 3064, using the parameter V, to determine the interpolated value 308 at the sampling position given by (U,V). Each of the five cubic interpolations described in this bicubic interpolation method can be performed in the same way as the cubic interpolation described above with reference to FIG. 3a. 